package main

import "fmt"
type BuildTreeNode struct {
	val int
	left *BuildTreeNode
	right *BuildTreeNode
}

func main()  {
	var pre = []int{3,9,20,15,7}
	var mid = []int{9,3,15,20,7}
	fmt.Println(buildTree(pre,mid))
}



func buildTree(preArr ,midArr []int) *BuildTreeNode  {
	if len(preArr) <= 0 || len(midArr) <= 0 {
		return nil
	}
    mid :=0
	for mid < len(midArr) && preArr[0] != midArr[mid] {
		mid++
	}

	var ret = new(BuildTreeNode)
	ret.left = buildTree(preArr[1:mid+1],midArr[:mid])
	ret.val = preArr[0]
	ret.right = buildTree(preArr[mid+1:],midArr[mid+1:])
    return ret
}
